public class Test7 {

    public static void main(String[] args) {
        int[][] a = {
                {9},
                {12, 15},
                {10, 6, 8},
                {2, 18, 9, 5},
                {19, 7, 10, 14, 6}
        };
        int result = triangleOfMath(a, 5, 5);
        System.out.println(result);
    }

    //m是行，n是列
    public static int triangleOfMath(int[][] a, int m, int n) {
        //1.创建dp表
        int[][] dp = new int[m + 1][n + 1];
        //2.填表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i - 1][j - 1];
            }
        }
        //3.返回值
        int result = 0;
        for (int i = 1; i <= n; i++) {
            result = Math.max(result, dp[m][i]);
        }
        return result;
    }
}
